//
//  46. 全排序.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/29.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
/**
 全排序问题
 所有数字重新排列
 */
class Solution46 {
    // 全排列
    // 全排序也是要通过页子节点取收集结果
    var result: [[Int]] = []
    var path: [Int] = []
    func permute(_ nums: [Int]) -> [[Int]] {
        backTrace(nums)
        return result
    }
    func backTrace(_ nums: [Int]) {
        for i in 0..<nums.count {
            var newNums = nums
            let removed = newNums.remove(at: i)
            path.append(removed)
            if newNums.count == 0 {
                result.append(path)
                path.removeLast()
            } else {
                backTrace(newNums)
                path.removeLast()
            }
        }
    }
    static func test(){
        let solution = Solution46()
        let nums = [1,2,3]
        let result = solution.permute(nums)
        print(result)
    }
}
